package main

import (
	"fmt"
	"math"
	"slices"
	"strings"
)

type Edge struct {
	u, v string
	w    float64
	next int
}

func (e *Edge) String() string {
	return fmt.Sprintf("%s->%s:%.0f", e.u, e.v, e.w)
}

type ForwardStar struct {
	n, m  uint
	head  []int
	cnt   int
	to    []*Edge
	nodes map[string]uint
	names map[uint]string
}

func NewForwardStart(names ...string) *ForwardStar {
	f := &ForwardStar{
		//names: make(map[uint]string),
		nodes: make(map[string]uint),
		names: make(map[uint]string),
	}
	for _, name := range names {
		_, ok := f.nodes[name]
		if !ok {
			f.nodes[name] = f.n
			f.names[f.n] = name
			f.n++
		}
	}
	f.head = make([]int, f.n)
	for i := range f.head {
		f.head[i] = -1
	}
	return f
}

func (f *ForwardStar) AddEdge(u, v string, w float64, undirected ...bool) {
	if !f.existNode(u) || !f.existNode(v) {
		fmt.Println("不存在顶点：", u, v)
		return
	}
	e := &Edge{
		u:    u,
		v:    v,
		w:    w,
		next: f.head[f.nodes[u]],
	}
	f.to = append(f.to, e)
	f.m++
	f.head[f.nodes[u]] = f.cnt
	f.cnt++
	if len(undirected) > 0 && undirected[0] {
		f.AddEdge(v, u, w)
	}
}

func (f *ForwardStar) existNode(name string) bool {
	_, ok := f.nodes[name]
	return ok
}

func (f *ForwardStar) FindEdge(u, v string) bool {
	if !f.existNode(u) || !f.existNode(v) {
		fmt.Println("不存在顶点：", u, v)
		return false
	}
	for j := f.head[f.nodes[u]]; j != -1; j = f.to[j].next {
		if f.to[j].v == v {
			return true
		}
	}
	return false
}

func (f *ForwardStar) FindOutEdges(u string, orderFunc func(a, b *Edge) int) (edges []*Edge) {
	if !f.existNode(u) {
		fmt.Println("不存在顶点：", u)
		return
	}
	for j := f.head[f.nodes[u]]; j != -1; j = f.to[j].next {
		edges = append(edges, f.to[j])
	}
	slices.SortStableFunc(edges, orderFunc)
	return
}

func (f *ForwardStar) Traverse(u string) {
	if !f.existNode(u) {
		fmt.Println("不存在顶点：", u)
		return
	}
	var dfs func(u string)
	vis := make([]bool, f.n)
	dfs = func(u string) {
		if vis[f.nodes[u]] {
			return
		}
		vis[f.nodes[u]] = true
		for j := f.head[f.nodes[u]]; j != -1; j = f.to[j].next {
			fmt.Printf("%s->%s:%3.0f\n", u, f.to[j].v, f.to[j].w)
			dfs(f.to[j].v)
		}
	}
	dfs(u)
}

func (f *ForwardStar) ShortestHeight(start string) (h []int, p []int, d []float64) {
	if !f.existNode(start) {
		panic("不存在节点")
	}
	u := f.nodes[start]
	h = make([]int, f.n)
	p = make([]int, f.n)
	d = make([]float64, f.n)
	for i := uint(0); i < f.n; i++ {
		h[i] = math.MaxInt
		p[i] = -1
		d[i] = math.Inf(1)
	}
	var q []uint
	vis := make([]bool, f.n)
	vis[u] = true
	h[u] = 0
	d[u] = 0
	q = append(q, u)

	for len(q) > 0 {
		u = q[0]
		q = q[1:]
		for j := f.head[u]; j != -1; j = f.to[j].next {
			v := f.nodes[f.to[j].v]
			if !(vis[v]) {
				q = append(q, v)
				vis[v] = true
				h[v] = h[u] + 1
				p[v] = int(u)
				d[v] = d[u] + f.to[j].w
			} else {
				if h[v] > h[u] && h[u] == h[p[v]] {
					minDist := math.MaxFloat64
					for j := f.head[p[v]]; j != -1; j = f.to[j].next {
						if f.nodes[f.to[j].v] == v {
							//multi-edge
							minDist = min(minDist, f.to[j].w)
						}
					}
					if d[u]+f.to[j].w < d[p[v]]+minDist {
						p[v] = int(u)
						d[v] = d[u] + f.to[j].w
					}
				}
			}
		}
	}

	return
}

func (f *ForwardStar) Restore(u, v string, p []int) string {
	if !f.existNode(u) || !f.existNode(v) {
		panic("Not Exist Node")
	}
	sb := new(strings.Builder)
	sb.WriteString(v)
	for j := p[f.nodes[v]]; j != -1; j = p[j] {
		sb.WriteString("<-" + f.names[uint(j)])
	}
	return sb.String()
}

func (f *ForwardStar) GetNodeNumber(u string) uint {
	return f.nodes[u]
}

type AdjacencyList struct {
}
